package ee.homework.third;

public class HeapSort2 {

	public static void main(String[] args) {
		HeapSort2 hs = new HeapSort2();
		int[] arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		hs.sort(arr);
		hs.printList(arr);
	}

	public void printList(int[] list) {
		for (int i = 0; i < list.length; i++) {
			System.out.print(list[i] + "  ");
		}
		System.out.println();
	}

	public void sort(int[] array) {
		int length = array.length;
		heapify(array, length);
		int end = length - 1;
		int tmp;

		while (end > 0) {
			tmp = array[0];
			array[0] = array[end];
			array[end] = tmp;
			end--;
			siftDown(array, 0, end);
		}
	}

	private void siftDown(int[] array, int start, int end) {
		int root = start;
		int child;
		int tmp;
		while (root * 2 + 1 <= end) {
			child = root * 2 + 1;
			if (child < end && array[child] < array[child + 1]) {
				child++;
			}
			if (array[root] < array[child]) {
				tmp = array[root];
				array[root] = array[child];
				array[child] = tmp;
				root = child;
			} else {
				return;
			}
		}
	}

	private void heapify(int[] array, int length) {
		int start = length / 2;
		while (start >= 0) {
			siftDown(array, start, length - 1);
			start--;
		}
	}
}
